package com.LeetCode.dp.shares;

import org.junit.Test;

/**
 * 买卖股票——Ⅳ 可以买卖 k次
 */
public class shares_4 {
    public int maxProfit(int[] prices, int  k){
        int len = prices.length;
        if(k < 1) return 0;
        if(k > len/2) return maxProfit_greedy(prices);

        //i: 第几次  j: 0 买 1 卖
        int[][] dp = new int[k][2];

        for(int i = 0; i<k; i++){
            dp[i][0] = Integer.MIN_VALUE;
        }

        for(int p : prices){
            //第一次买 还是 不买
            dp[0][0] = Math.max(dp[0][0] , 0 - p);
            //第一次卖 还是 不卖
            dp[0][1] = Math.max(dp[0][1] , dp[0][0] + p);
            for(int i = 1; i<k; i++){
                //第 i 次买 还是 不买
                dp[i][0] = Math.max(dp[i][0] , dp[i-1][1] - p);
                //第 i 次卖 还是 不卖
                dp[i][1] = Math.max(dp[i][1] , dp[i][0] + p);
            }
        }
        return dp[k-1][1];
    }

    public int maxProfit_greedy(int[] prices){
        int len = prices.length;
        int res = 0;
        for(int i = 1; i<len; i++){
            res = prices[i] > prices[i-1] ? res + prices[i] - prices[i-1] : res;
        }
        return res;
    }

    @Test
    public void test(){
        int[] arr = {3,2,6,5,0,3};
        int k = 2;
        System.out.println(maxProfit(arr,k));
    }
}
